package com.kingwood.algorithm.zuochengyun.dandiaoduilie;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/14 10:46
 * @Modified By：
 * @Version 1.0
 */
public class Test {

    public static int MAXN = 100001;

    public static int[] deque = new int[MAXN];

    public static int h, t;

    public static int[] SlideWindowMax(int[] arr, int k) {
        h = t = 0;
        int n = arr.length;
        int m = n - k + 1;
        int[] ans = new int[m];

        // 先形成长度为k-1的窗口
        for (int i = 0; i < k - 1; i++) {
            // 大 -> 小
            while (h < t && arr[deque[t - 1]] <= arr[i]) {
                t--;
            }
            deque[t++] = i;
        }

        for (int l = 0, r = k - 1; l < m; l++, r++) {
            // 大 -> 小
            // 少一个，要让r位置的数进来
            while (h < t && arr[deque[t-1]] < arr[r]) {
                t--;
            }

            deque[t++] = r;
            // 收集答案
            ans[l] = arr[deque[h]];
            // l位置的数出去
            if (deque[h] == l) {
                h++;
            }
        }

        return ans;

    }

    public static void main(String[] args) {

    }
}
